网络表征学习中的基本问题初探

阅读量:789
王啸 ,崔鹏,朱文武

网络表征学习的必要性

真实世界中的复杂系统通常都可以构建为网络形式,比如社交网络、生物网络等。为了更好地支持基于网络数据的应用,如何有效地表示网络是关键步骤。而随着网络数据规模的快速增大,传统的基于网络拓扑的表征方式显露出愈加明显的缺陷。

首先,由于拓扑结构通常导致许多网络的分析与处理算法需要许多迭代和组合计算步骤,因而不可避免地产生高复杂度运算的问题。比如,为了评估网络中一个节点的重要性,我们不得不首先评估其邻居节点的重要性,以此类推,直到评估完所有节点的重要性。这种高复杂度的处理过程极大阻碍了相应算法在大规模网络上的应用。

其次,由于拓扑关系表示节点之间有着强耦合关系,使得并行和分布式运算很难被直接应用到网络数据。由于节点之间边的存在,如果简单地将不同节点分配到不同的服务器上运算,则服务器之间需要频繁地通信,因此严重影响加速比。

第三,目前机器学习尤其是深度学习已经在许多领域显示出强大的数据处理能力,对许多问题都已给出了有效的解决方案。但是它们针对的数据表征通常为一个向量空间中的独立性数据,而非彼此关联的非独立性网络数据,这会导致很多有效解决方案无法直接应用到网络数据上,而必须重新设计基于网络拓扑的模型。由此可见,传统的基于网络拓扑的表征方式已经成为限制大规模网络处理和分析的瓶颈。近年来,不少研究者开始关注网络表征学习领域[1],研究如何为网络中的节点学习一个低维空间中的有效向量表征,从而更好地支持后续的网络应用。图1展示了基于网络表征学习的网络分析摆脱了邻接矩阵中边的约束,使得每个节点成为低维空间中的独立数据,进而基于这种向量表达解决后续的应用问题。

网络表征学习已经在多种网络处理和分析任务上验证了其有效性,比如节点分类[1]、链路预测[2]以及网络可视化[3]。网络表征学习需要在低维空间中学习节点的稠密且连续的表征,使得观测的网络结构中的噪音或者冗余信息可以被去除,同时本质的结构信息得以保持。相比于传统的节点表征方法,这种节点表征的优势是显而易见的。比如节点已经不再有耦合关系,使一些主流的并行计算方案应用在大规模网络上变得可行。同样,网络表征学习也为利用机器学习工具处理网络数据提供了新的机遇,许多现有的机器学习方法可以直接引入过来解决网络问题。

为了让网络表征更好地支持下游的网络分析任务,网络表征学习通常有两个基本目标。一是在低维空间中学习到的表征可以重构出原有网络结构,这就要求,如果两个节点有边连接,则它们在低维空间中的距离接近,否则,它们的距离就较远。第二个目标是学习到的表征可以有效地支持网络推断。只实现第一个目标在实际中并不足以支持网络推断任务。以链路预测为例,如果只考虑第一个目标,一些学习算法会倾向于完美拟合邻接矩阵中所有的01,而这种处理方式容易受到过拟合的影响,对未知边的推断会起到负面作用。

从图嵌入到网络表征学习

图嵌入算法的目的与网络表征学习有相似的地方。图嵌入也是根据一个图,学习图中节点的低维表征,代表性的算法有Isomap[4], LLE[5]LE[6]。这些传统图嵌入算法的基本思路是基于某种规则,比如KNN方法,从图像或文本数据集中构建一个相似度矩阵,利用降维方法学习得到每个数据的表征,该表征可以保持这种构建的图的结构。所以本质上图嵌入算法重点关注网络表征学习的第一个目标,即保持图的结构。传统图嵌入方法所针对的数据实际上是图像或文本等非结构化数据,所要达到的目的是学习图像或文本的表征。他们所采用的图通过计算数据之间的相似度得到,而并非是真实世界中的网络,这种相似度一旦通过计算得到,就认为表示了数据之间的准确关系。可真实世界中网络之间的边,通常只表示节点之间存在着关系,节点之间具体的相似度还需要根据具体任务去计算,这也是为何在网络表征学习中,为了更好地支持网络推断,除了现有观测到的网络边之外,我们还需要进一步考虑网络的高阶结构、网络的性质等。

会员登录后可下载全文

中国计算机学会(CCF)拥有《中国计算机学会通讯》(CCCF)所刊登内容的所有版权,未经CCF允许,不得转载本刊文字及照片,否则被视为侵权。对于侵权行为,CCF将追究其法律责任。
读完这篇文章后,您心情如何?

作者介绍

王啸

崔鹏

  • CCF专业会员
  • 清华大学计算机系副教授
  • 研究方向:社会网络分析与社 会媒体计算。
  • cuip@tsinghua.edu.cn

朱文武

  • CCF 杰出会员
  • 清华大学教授
  • 研究方向:三元空间大数据计算和跨媒体 智能推理等
  • wwzhu@tsinghua.edu.cn